package week7;

import java.util.*;

/**
 *
 *
 * 127. 单词接龙
 * https://leetcode-cn.com/problems/word-ladder/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：25 ms, 在所有 Java 提交中击败了88.56% 的用户
 * 内存消耗：48.5 MB, 在所有 Java 提交中击败了5.48% 的用户
 * 通过测试用例：49 / 49
 * 炫耀一下:
 *
 *
 */
public class Week7WordLadder {

    Map<String, Integer> wordNumMap = new HashMap<String, Integer>();
    List<List<Integer>> edgeList = new ArrayList<List<Integer>>();
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for(String word : wordList) {
            appendEdge(word);
        }
        appendEdge(beginWord);
        if(!wordNumMap.containsKey(endWord)) {
            return 0;
        }
        int[] destination = new int[nodeNum];
        Arrays.fill(destination, Integer.MAX_VALUE);
        int beginId = wordNumMap.get(beginWord);
        int endId = wordNumMap.get(endWord);
        destination[beginId] = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(beginId);
        for(;!queue.isEmpty();) {
            int x = queue.poll();
            if(x == endId) {
                return destination[endId] / 2 + 1;
            }
            for(int it : edgeList.get(x)) {
                if(destination[it] == Integer.MAX_VALUE) {
                    destination[it] = destination[x] + 1;
                    queue.offer(it);
                }
            }
        }

        return 0;
    }

    public void appendEdge(String word) {
        appendWord(word);
        int beforeNum = wordNumMap.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for(int size = 0; size < length; size++) {
            char temp = array[size];
            array[size] = '*';
            String newWord = new String(array);
            appendWord(newWord);
            int currentNum = wordNumMap.get(newWord);
            edgeList.get(beforeNum).add(currentNum);
            edgeList.get(currentNum).add(beforeNum);
            array[size] = temp;
        }
    }

    public void appendWord(String word) {
        if(!wordNumMap.containsKey(word)) {
            wordNumMap.put(word, nodeNum++);
            edgeList.add(new ArrayList<Integer>());
        }
    }
}
